Task #R102D

Nodir is a student who loves mathematics. He enjoys discovering interesting patterns in numbers. One day, while analyzing the order of digits, he noticed a strange property: some numbers have a specific sequence of odd and even digits.

For example, numbers like 10, 12, 14, 16, 18, 21, 23, ... have digits that follow an alternating odd-even or even-odd pattern. Nodir called such numbers "amazing numbers." He found that the first amazing number is 10 and wrote down all numbers that follow this pattern.

Now, Nodir is trying to solve a problem: how can he quickly find the N-th amazing number? Can you help him?

The first line contains an integer \(T (1 ≤ T ≤ 10⁵)\), the number of test cases.

The next T lines contain a single integer \(N (1 ≤ N ≤ 10¹⁸)\), representing the position of the amazing number that needs to be found.

For each test case, print the N-th amazing number on a separate line.